package day_2022_12_to_3.year2023;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/01/18 22:18
 **/
public class Day1_18_Review {
    class Solution32 {
        public int[] levelOrder(TreeNode root) {
            if(root == null) return new int[0];
            Deque<TreeNode> q = new LinkedList<>();
            q.offer(root);
            List<Integer> res = new LinkedList<>();
            while(!q.isEmpty()) {
                int size = q.size();
                for(int i = 0; i < size; ++i) {
                    TreeNode cur = q.poll();
                    res.add(cur.val);
                    if(cur.left != null) q.offer(cur.left);
                    if(cur.right != null) q.offer(cur.right);
                }
            }
            return res.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class Solution32_Ⅱ {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            levelOrderHelper(root, 0);
            return res;
        }
        public void levelOrderHelper(TreeNode root, int k) {
            if(root == null) return;
            if(res.size() <= k) res.add(new LinkedList<>());
            res.get(k).add(root.val);

            levelOrderHelper(root.left, k + 1);
            levelOrderHelper(root.right, k + 1);
        }
    }

    class Solution32_Ⅲ {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            levelOrderHelper(root, 0);
            return res;
        }
        public void levelOrderHelper(TreeNode root, int k) {
            if(root == null) return;
            if(res.size() <= k) res.add(new LinkedList<>());
            if(k % 2 == 0) res.get(k).add(root.val);
            else res.get(k).add(0, root.val);

            levelOrderHelper(root.left, k + 1);
            levelOrderHelper(root.right, k + 1);
        }
    }

    class Solution33 {
        public boolean verifyPostorder(int[] postorder) {
            return verifyPostorderHelper(postorder, 0, postorder.length-1);
        }
        public boolean verifyPostorderHelper(int[] postorder, int l, int r) {
            if(l > r) return true;
            int m = l;
            while(postorder[m] < postorder[r]) m++;
            int p = m;
            while(postorder[p] > postorder[r]) p++;
            return p == r && verifyPostorderHelper(postorder, l, m-1) && verifyPostorderHelper(postorder, m, r-1);
        }
    }
}